package my;

import my.util.ArrayList;
import my.util.List;
import my.util.circle.CircleLinkedList;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

/**
 * <p>
 * 链表-LinkedList
 * </p>
 *
 * @author AJun
 * @since 2020/8/12
 */
public class Main03 {

    static void testList(List<Integer> list) {
        list.add(11);
        list.add(22);
        list.add(33);
        list.add(44);

        list.add(0, 55); // [55, 11, 22, 33, 44]
        list.add(2, 66); // [55, 11, 66, 22, 33, 44]
        list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

        list.remove(0); // [11, 66, 22, 33, 44, 77]
        list.remove(2); // [11, 66, 33, 44, 77]
        list.remove(list.size() - 1); // [11, 66, 33, 44]

        assertEquals(3, list.indexOf(44));
        assertEquals(list.indexOf(22), -1);
        assertTrue(list.contains(33));
        assertEquals(11, (int) list.get(0));
        assertEquals(66, (int) list.get(1));
        assertEquals(44, (int) list.get(list.size() - 1));

        System.out.println(list);
    }

    // 约瑟夫问题
    static void josephus(int n) {
        CircleLinkedList<Integer> list = new CircleLinkedList<>();
        List<Integer> result = new ArrayList<>(); // 存放死去的人的序列
        for (int i = 1; i <= 8; i++) {
            list.add(i);
        }

        // 将 current 指向头节点(即: 指向 1)
        list.reset();

        Integer target = -1;
        while (!list.isEmpty()) {
            int i = n;
            // 将 current 后移俩个位置，即: 数三次
            while ((i--) > 1) {
                list.next();
            }
            // 删除 current 当前指向的节点，并将 current 后移一个位置
            target = list.remove();
            result.add(target);
        }
        result.remove(result.size() - 1); // 最后一个为活下来的人
        System.out.println("死去的人的序列 => " + result);
        System.out.println("活下来的人 => " + target);
    }

    public static void main(String[] args) {
        // testList(new ArrayList<>());
        // testList(new SingleLinkedList<>());
        // testList(new SingleLinkedListVirtualHead<>());
        // testList(new LinkedList<>());
        // testList(new SingleCircleLinkedList<>());
        // testList(new CircleLinkedList<>());

        // 约瑟夫问题
        josephus(3);
    }

}
